/*
实验8-4 最小生成树的唯一性
分数 35
作者 陈越
单位 浙江大学

给定一个带权无向图，如果是连通图，则至少存在一棵最小生成树，有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重，并且判断其是否唯一。
输入格式：

首先第一行给出两个整数：无向图中顶点数 N（≤500）和边数 M。随后 M 行，每行给出一条边的两个端点和权重，格式为“顶点1 顶点2 权重”，其中顶点从 1 到N 编号，权重为正整数。题目保证最小生成树的总权重不会超过 230。
输出格式：

如果存在最小生成树，首先在第一行输出其总权重，第二行输出“Yes”，如果此树唯一，否则输出“No”。如果树不存在，则首先在第一行输出“No MST”，第二行输出图的连通集个数。
输入样例 1：

5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5

输出样例 1：

11
Yes

输入样例 2：

4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

输出样例 2：

4
No

输入样例 3：

5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

输出样例 3：

No MST
2
*/

#include "../base/UnionFind.cpp"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义边的结构
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

bool isMSTUnique(int n, vector<Edge>& edges, vector<Edge>& mstEdges, int mstWeight) {
    // 检查是否存在其他 MST
    for (size_t i = 0; i < mstEdges.size(); ++i) {
        UnionFind ufTemp(n);
        int tempWeight = 0;
        vector<Edge> tempEdges;

        // 跳过当前边，尝试用其他边替换
        for (size_t j = 0; j < edges.size(); ++j) {
            if (edges[j].weight == mstEdges[i].weight && edges[j].u != mstEdges[i].u && edges[j].v != mstEdges[i].v) {
                if (!ufTemp.same(edges[j].u, edges[j].v)) {
                    ufTemp.merge(edges[j].u, edges[j].v);
                    tempEdges.push_back(edges[j]);
                    tempWeight += edges[j].weight;
                }
            } else if (edges[j].weight != mstEdges[i].weight) {
                if (!ufTemp.same(edges[j].u, edges[j].v)) {
                    ufTemp.merge(edges[j].u, edges[j].v);
                    tempEdges.push_back(edges[j]);
                    tempWeight += edges[j].weight;
                }
            }
        }

        // 如果找到另一个 MST，则 MST 不唯一
        if (tempEdges.size() == mstEdges.size() && tempWeight == mstWeight) {
            return false;
        }
    }

    return true;
}

void buildMst(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    int total_weight = 0;
    vector<Edge> mstEdges;
    for (int i = 0; i < edges.size(); ++i) {
        if (!uf.same(edges[i].u, edges[i].v)) {
            uf.merge(edges[i].u, edges[i].v);
            total_weight += edges[i].weight;
            mstEdges.push_back(edges[i]);
        }
    }
    int set_count = uf.get_set_count(1);
    if (set_count > 1) {
        cout << "No MST" << endl;
        cout << set_count << endl;
    } else {
        cout << total_weight << endl;
        cout << (isMSTUnique(n, edges, mstEdges, total_weight) ? "Yes" : "No") << endl;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    }
    buildMst(edges, n);
    return 0;
}